package primary.primary0;


/**
 * 动态规划
 */
public class S0096不同的二叉搜索树 {
    class Solution {

        /**
         * 100, 43
         * 感觉可以用动态规划，我是这样想的，一个形状一定只会对应一种dfs的排列
         * 所以，好比是一个1~n的递增数组，我随机选择其中一个数j当根节点，那么，j左边的就是他的左子树，j右边的就是他的右子树
         * 也就是说，j当根节点的排列数量为 左子树可能的数量*右子树可能的数量
         */
        public int numTrees(int n) {
            // i位置表示i个节点有多少种方法
            int[] record = new int[n + 1];
            record[0] = 1;
            for (int i = 1; i <= n; i++) {
                for (int j = 0; j <= i - 1; j++) {
                    record[i] += record[j] * record[i - j - 1];
                }
            }
            return record[n];
        }
        /**
         * 二叉搜索树就是左边<中间<右边的
         * 二叉搜索树的 dfs 左中右 遍历，会得到一个递增数组
         * 不考虑二叉搜索树，n个节点能组成多少个形状的?一个形状会存在两种二叉搜索树吗?
         * dfs递增，所以一个二叉搜索树一定只能塞进去一种数值。
         * 先求多少种树，
         * mark: 二叉搜索树特征，dfs种类
         */
        public int numTrees0(int n) {
            int typesWithOrder = 1;// 逐个放置节点，记顺序的话，有多少种
            for (int i = 1; i < n; i++) {
                typesWithOrder = typesWithOrder * i;
            }
            return -1;
        }
    }
}
